package Sort.sort;
//������ ʱ�临�Ӷ�Ϊn(logn)
public class HeapSort {

	public static void main(String[] args) {
       int[] array = {4,5,1,2,10,7,3,8};
       for(int i=0;i<array.length;i++){
    	   System.out.print(array[i]);
    	   System.out.print(" ");
       }
       heapSort(array);
       System.out.println();
       for(int i=0;i<array.length;i++){
    	   System.out.print(array[i]);
    	   System.out.print(" ");
       }
	}
    public static void heapSort(int[] array){
    	if(array==null||array.length==0){
    		return;
    	}
    	for(int i=array.length/2-1;i>=0;i--){
    		heapAdjust(array,i,array.length-1);
    	}
    	for(int i=array.length-1;i>=0;i--){
    		int temp = array[i];
    		array[i] =array[0];
    		array[0] = temp;
    		heapAdjust(array, 0, i - 1);
    	}
    }
    public static void heapAdjust(int[] array,int index,int end){
          int j;
          for(j=2*index+1;j<=end;j=2*j+1){/*ע�⣺����ѭ������ΪֻҪ���ֽ��������Ҫ���±Ƚ�*/
        	  if(j<end&&array[j]<array[j+1]){
        		  j++;
        	  }
        	  if(array[index]>=array[j]){
        		  break;
        	  }
        	  int temp = array[index];
        	  array[index] = array[j];
        	  array[j] = temp;
        	  index=j;
          }
    }
}
